package com.cat.greedyAlgorithm;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-division-operations-to-make-array-non-decreasing/
 * @create 2025/10/9 15:00
 * @since JDK17
 */

public class Solution63 {
    int ans;
    int get(int num) {
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return num / i;
            }
        }
        return -1;
    }

    public int minOperations(int[] nums) {
        int n = nums.length;
        for (int i = n - 2; i >= 0; i--) {
            while (nums[i] > nums[i + 1]) {
                int t = get(nums[i]);
                if (t == -1) {
                    return -1;
                }
                nums[i] /= t;
                ans++;
            }
        }

        return ans;
    }
}
